/********************************************************************************
 * @Author: Zhenzhou Liu
 * @Date: 2024-12-28
 * @Description: Cg贪心练习之霍夫曼编码
 * TODO: 测试样例的输出格式未指定
 *******************************************************************************/
#include <iostream>
#include <queue>

using namespace std;

struct HuffmanNode {
    char ch;
    int freq;
    HuffmanNode *left;
    HuffmanNode *right;
    HuffmanNode(char c, int freq) {
        this->ch = c;
        this->freq = freq;
        this->left = nullptr;
        this->right = nullptr;
    }
    HuffmanNode(char c, int freq, HuffmanNode *left, HuffmanNode *right): ch(c), freq(freq), left(left), right(right) {};

    bool operator<(const HuffmanNode &other) const {
        return freq > other.freq;
    }
};

struct compare {
    bool operator() (const HuffmanNode *a, const HuffmanNode *b) {
        return a->freq > b->freq;
    }
};

HuffmanNode *buildHuffmanTree(const unordered_map<char, int> &charFreq) {
    priority_queue<HuffmanNode*, vector<HuffmanNode*>, compare> pq;
    for (pair<char, int> entry : charFreq) {
        pq.push(new HuffmanNode(entry.first, entry.second));
    }

    while (pq.size() > 1) {
        HuffmanNode* left = pq.top();
        pq.pop();
        HuffmanNode* right = pq.top();
        pq.pop();
        pq.push(new HuffmanNode('#', left->freq + right->freq, left, right));
    }
    return pq.top();
}

void generateCodes(HuffmanNode *root, string code, unordered_map<char, string> &huffmanCode) {
    if (root == nullptr) {
        return;
    }
    if (root->left == nullptr && root->right == nullptr) {
        huffmanCode[root->ch] = code;
    }
    generateCodes(root->left, code + "0", huffmanCode);
    generateCodes(root->right, code + "1", huffmanCode);
}

void freeHuffmanTree(HuffmanNode * root) {
    if (root == nullptr)
        return;
    freeHuffmanTree(root->left);
    freeHuffmanTree(root->right);
    delete root;
}

int main() {
    string input;
    cin >> input;
    unordered_map<char, int> charFreq;
    for (char c : input) {
        if (charFreq.count(c) == 0) {
            charFreq[c] = 0;
        }
        charFreq[c]++;
    }
    HuffmanNode *root = buildHuffmanTree(charFreq);
    unordered_map<char, string> huffmanCode;
    generateCodes(root, "", huffmanCode);

    string output;
    for (char ch : input) {
        output += huffmanCode[ch];
    }
    cout << output << endl;

    freeHuffmanTree(root);
    return 0;
}

